The present invention relates to a method for providing fair allocation of bandwidth in a communication system. More particularly, the present application is directed to a method for allocating bandwidth in a network in which a plurality of sources can request a bandwidth allocation and the network then determines how to allocate the bandwidth among the sources.
As people continue to expand the ways in which they communicate, data communication between users of a network has become more and more critical. Data can represent many different things, for example video images, facsimiles, processing data. There is tremendous demand for greater and greater data transfer capabilities. Many different network arrangements have been proposed for facilitating the transfer of data. Among them have been networks referred to as Asynchronous Transfer Mode (ATM) networks.
It has been recognized, however, that even in networks which are better suited for the transfer of data, such as ATM networks, it is necessary to allocate network resources, such as bandwidth typically described in terms of a bit rate, among more and more demanding sources of data.
Rate-based congestion management has been proposed for feedback control of ATM networks. A number of different services have been proposed for the ATM networks including a service referred to as Available-Bit-Rate (ABR) service. This service has been considered to be effective for transmitting bursty data where there is no clear specification of the source's characteristics. The service provides an explicit rate feedback control by: receiving a resource management cell from a source, which cell designates the source's demand for rate allocation; each switch along the connection from a source to a destination identifies and conveys its own congestion state back to the source-end system via the resource management cell.
An example of a network configuration in which the ABR scheme may be employed is illustrated in FIG. 1. Here there are four data sources, 10, 11, 12 and 13 respectively, each sending data to one of four destinations, 20, 21, 22 and 23 respectively. The data communications are transmitted via the ATM network 30 which contains a plurality of switches, for example 31, 32, 33 and 34. Assume that the first data source 10 is transmitting data to the first destination 20 via switches 31 and 32. Switch 31 also receives data from the fourth source 13. Thus, switch 31 must allocate its channel capacity between these two data sources. Each data source will submit a resource management (RM) cell to request a particular bit rate be allocated. If switch 31 has sufficient capacity to satisfy the demand from both source 10 and source 13 then it will grant the demand from the sources and will be able to send all of the data to switch 32. The data will include the resource management cells transmitted from the sources. Since both sources have been satisfied the resource management cell will continue to include the demanded rate, without being marked down at any switch. Assume for a moment that switch 33 receives the resource management cells from data sources 11 and 12 and that because of its channel capacity the switch cannot satisfy both of these sources. Then the switch must allocate the channel bandwidth between the two sources. Assume for a moment that both sources demand more than half of the channel capacity of switch 33 and the switch by its allocation algorithm assigns half the channel capacity to each source, then both sources remain unsatisfied and the switch overwrites the resource management cells replacing the Demands with the explicit rate (ER) allocated by switch 33. Then, as switch 33 sends the data from sources 11 and 12 to switch 32, the resource management cells reflect the congestion arising at switch 33. As the RM cell for a source flows to its destination the ER field can be overwritten (marked down) any number of times (once at each switch it traverses, where the capacity that can be allocated successively reduces). The source is then notified of the allowed or allocated rate when the modified RM cell is returned to the source.
There are known techniques for performing the allocation. For instance the allocation that will subsequently take place at switch 32 could use a simple process to allocate a share of capacity to each competing source. In particular, the allocation at switch 32 could rely upon comparing the overall channel capacity of 32 to the total capacity requested by the various sources in accordance with the state of the resource management cell as it is received at switch 32. Thus, the determination at switch 32 is based on decisions made by switches upstream, that is the congestion rates exemplified by modified RM cells, and does not take into account the actual demand initially sent to the network by the various data sources. This can be disadvantageous since as between certain sources having the same explicit rate (ER) in the RM cell defined for them by upstream switches, one of those data sources may have a dramatically higher demand which is provided in the hopes of maintaining a certain data quality, for instance in a video environment. Thus, the known allocation algorithms do not adequately account for the needs of the data sources, but instead are very heavily dependent on the state of congestion at upstream bottlenecks.